|
In graph theory, nowhere-zero flows are a special type of network flow which is related (by duality) to coloring planar graphs. == Definition == Let ''G'' = ''(V,E)'' be a directed graph and let ''M'' be an abelian group. A map φ: ''E'' → ''M'' is a flow or an ''M''-flow if for every vertex ''v'' ∈ ''V'', it holds that : where ''δ+(v)'' denotes the set of edges out of ''v'' and ''δ−(v)'' denotes the set of edges into ''v''. Sometimes, this condition is referred to as Kirchhoff's law. If ''φ(e)'' ≠ 0 for every ''e'' ∈ ''E'', we call φ a nowhere-zero flow. If ''M'' = Z is the group of integers under addition and ''k'' is a positive integer with the property that –''k'' < ''φ(e)'' < ''k'' for every edge ''e'', then the ''M''-flow φ is also called a ''k''-flow. Let ''G'' = ''(V,E)'' be an undirected graph. An orientation of ''E'' is a modular ''k''-flow if : for every vertex ''v'' ∈ ''V''. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Nowhere-zero flow」の詳細全文を読む スポンサード リンク
|